package leetcode;

public class Q0074 {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (target < matrix[0][0] || target > matrix[matrix.length - 1][matrix[0].length - 1]) return false;
        int l = 0;
        int r = matrix.length - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (matrix[mid][0] <= target) l = mid;
            else r = mid - 1;
        }
        int x = l;

        l = 0;
        r = matrix[0].length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (matrix[x][mid] >= target) r = mid;
            else l = mid + 1;
        }

        return matrix[x][l] == target;
    }
}
